#include "cursorList.h"

template <class Object>
void List<Object>::initializeCursorSpace()
{
	static int cursorSpaceInitialized = false;

	if ( !cursorSpaceInitialized ) {
		cursorSpace.resize(100);	
		for (int i = 0; i < cursorSpace.size(); i++)
			cursorSpace[i].next = i+1;
		cursorSpace[cursorSpace.size() - 1].next = 0;
		cursorSpaceInitialized = true;
	}
}

template <class Object>
int List<Object>::alloc()
{
	int p = cursorSpace[0].next;
	cursorSpace[0].next = cursorSpace[p].next;
	return p;
}

template <class Object>
void List<Object>::free(int p)
{
	cursorSpace[p].next = cursorSpace[0].next;
	cursorSpace[0].next = p;
}

template <class Object>
List<Object>::List()
{
	initializeCursorSpace();
	header = alloc();
	cursorSpace[header].next = 0;
}

template <class Object>
List<Object>::~List()
{
	makeEmpty();
	free(header);
}

template <class Object>
bool List<Object>::isEmpty() const
{
	return cursorSpace[header].next == 0;
}

template <class Object>
ListItr<Object> List<Object>::first() const
{
	return ListItr<Object>(cursorSpace[header].next);
}

template <class Object>
ListItr<Object> List<Object>::find(const Object &x) const
{
	int itr = cursorSpace[header].next;

	while (itr != 0 && cursorSpace[itr].element != x)
		itr = cursorSpace[itr].next;
	
	return ListItr<Object>(itr);
}

template <class Object>
void List<Object>::insert(const Object &x, const ListItr<Object> &p)
{
	if (p.current == 0) {
		int pos = p.current;
		int tmp = alloc();

		cursorSpace[tmp] = CursorNode(x, cursorSpace[pos].next);
		cursorSpace[pos].next = tmp;
	}
}

template <class Object>
void List<Object>::remove(const Object &x)
{
	ListItr<Object> p = findPrevious(x);
	int pos = p.current;

	if (cursorSpace[pos].next != 0) {
		int tmp = cursorSpace[pos].next;
		cursorSpace[pos].next = cursorSpace[tmp].next;
		free(tmp);
	}
}
